import org.junit.Test;
import test.TreeNode;

/**
 * 平衡二叉树
 */
public class isBalanced {

    @Test
    public void test() {
        TreeNode treeNode = new TreeNode(1);
        TreeNode right = new TreeNode(12);
        TreeNode left21 = new TreeNode(211);
        TreeNode right22 = new TreeNode(222);
        right.setLeft(left21);
        right.setRight(right22);
        treeNode.setRight(right);
        TreeNode left1 = new TreeNode(11);
        TreeNode left11 = new TreeNode(111);
        TreeNode right12 = new TreeNode(122);
        left1.setLeft(left11);
        left1.setRight(right12);
        treeNode.setLeft(left1);
        System.out.println(test(treeNode));
    }

    public boolean test(TreeNode root) {
        if (root == null) {
            return true;
        }
        return helper(root) != -1;
    }

    private int helper(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = helper(root.getLeft());
        int right = helper(root.getRight());
        if (left == -1 || right == -1 || Math.abs(left - right) > 1) {
            return -1;
        }
        return Math.max(left, right) + 1;
    }

}
